#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: unique_paths.py 
@version:
@time: 2023/12/24 
"""


def unique_paths(m, n):
    dp = []

    for i in range(n):
        dp.append([0] * m)
    # 初始化dp

    for i in range(n):
        dp[i][0] = 1
    dp[0] = [1] * m
    # 显而易见，想到达网络的第一行或者第一列都只有一种路径，
    # 到达第一行只能通过向右走，到达第一列只能通过向下走，
    # 因此初始化时，第一行第一列初始化为1，其他位置为0.

    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[n - 1][m - 1]


print(unique_paths(7, 3))
